package com.company.ljh.medium;

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Random;

/**
 * @description:
 * @projectName:leet_code
 * @see:com.company.ljh.medium
 * @author:ljh
 * @createTime:2023/7/6 18:11
 * @version:1.0
 */
public class 数组中的第K个最大元素 {
    public static Random random = new Random(System.currentTimeMillis());

    public static void main(String[] args) {
        findKthLargest(new int[]{3,2,3,1,2,4,5,5,6},4);
    }
    public static int findKthLargest(int[] nums, int k) {
        //使用快排查找k大的数
        int result = fastSort(nums, 0, nums.length - 1, nums.length - k);
        return result;
    }
    //优先级队列，小跟堆
    public static int findKthLargest2(int[] nums, int k) {
        //小根堆，最小的放顶
        PriorityQueue<Integer> queue= new PriorityQueue<Integer>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1-o2;
            }
        });
        for (int num:nums){
            queue.offer(num);
            if (queue.size() > k){
                //将最小的出队
                queue.poll();
            }
        }
        return queue.peek();
    }
    public static int fastSort(int[] nums,int start,int end ,int findIndex){
        //随机选取一个数作为比较
        int pivot = start + random.nextInt(end - start+1);
        int pivotNum = nums[pivot];
        //将数交换到开头
        swap(nums,start,pivot);
        int leftIndex = start;
        int rightIndex = end;
        int i = leftIndex+1;
        while(leftIndex < rightIndex){
            if(nums[i] <= pivotNum){
                swap(nums,i,leftIndex++);
            }else{
                swap(nums,i,rightIndex--);
            }
            i++;
        }
        if(leftIndex == findIndex){
            return nums[findIndex];
        }
        if(leftIndex < findIndex){
            return fastSort(nums,leftIndex+1,end,findIndex);
        }else{
            return fastSort(nums,start,leftIndex-1,findIndex);
        }
    }
    private static void swap(int nums[],int index1,int index2){
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }
}
